#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int ElemType;
typedef struct
{
    ElemType *elem;
    int Tablelen;
}SSTable;
void InitSStable(SSTable &ST,int length)
{
    ST.Tablelen=length;
    ST.elem=(ElemType*) malloc(sizeof (ElemType)*ST.Tablelen);
    int i;
    srand(time(NULL));
    for(i=0;i<ST.Tablelen;i++)
    {
        ST.elem[i]=rand()%100;
    }
}
void SStablePrint(SSTable ST)
{
    int i;
    for (i=0;i<ST.Tablelen;i++)
    {
        printf("%3d",ST.elem[i]);
    }
    printf("\n");
}
int BinarySearch(SSTable ST,ElemType k)
{
    int low=0;
    int high=ST.Tablelen-1;
    int mid;
    while(low<=high)
    {   mid=(low+high)/2;
        if (k>ST.elem[mid])
        {
            low=mid+1;
        }
        else if (k<ST.elem[mid])
        {
            high=mid-1;
        }
        else if (k==ST.elem[mid])
        {
            return mid;
        }
    }
    return -1;
}
int compare(const void *left,const void *right)//qsort规定如果left指针大于指向right指针的值，返回正值，如果小于返回负值，相等为0
//left和right指针是指向数组中的任意两个元素
{
    return *(int*)left-*(int*)right;
}
int main()
{
    SSTable ST;
    InitSStable(ST,10);
    SStablePrint(ST);
    qsort(ST.elem,ST.Tablelen,sizeof(ElemType),compare);
    SStablePrint(ST);
    ElemType key;
    scanf("%d",&key);
    int pos=BinarySearch(ST,key);
    if (pos!=-1)
    {
        printf("key is %d",pos);
    }
    else{
        printf("not found");
    }
    return 0;
}